// @author U095159L VARUN GANESH
// all functions in this file  are implemented by the author unless specifically indicated
function a_star(current_position, player_position, grid, columns, rows, allow_diagonals)
{
	//Create current_position and player_position as true nodes
	current_position = new node(current_position[0], current_position[1], -1, -1, -1, -1);
	player_position = new node(player_position[0], player_position[1], -1, -1, -1, -1);

	var open = []; //List of open nodes (nodes to be inspected)
	var closed = []; //List of closed nodes (nodes we've already inspected)

	var g = 0; //Cost from current_position to current node
	var h = heuristic(current_position, player_position); //Cost from current node to player_position
	var f = g+h; //Cost from current_position to player_position going through the current node

	//Push the current_position node onto the list of open nodes
	open.push(current_position); 

	if(current_position.x < 0 || current_position.x >= columns || current_position.y < 0 || current_position.y >= rows){
		return [];
	}
	else if(player_position.x < 0 || player_position.x >= columns || player_position.y < 0 || player_position.y >= rows){
		return[];
	}
	else{
		//Keep going while there's nodes in our open list
		var lag_timer = 100;
		while (open.length > 0 && lag_timer > 0)
		{
			lag_timer--;
			//Find the best open node (lowest f value)

			//Alternately, you could simply keep the open list sorted by f value lowest to highest,
			//in which case you always use the first node
			var best_cost = open[0].f;
			var best_node = 0;

			for (var i = 1; i < open.length; i++)
			{
				if (open[i].f < best_cost)
				{
					best_cost = open[i].f;
					best_node = i;
				}
			}

			//Set it as our current node
			var current_node = open[best_node];

			//Check if we've reached our player_position
			if (current_node.x == player_position.x && current_node.y == player_position.y)
			{
				var path = [player_position]; //Initialize the path with the player_position node

				//Go up the chain to recreate the path 
				while (current_node.parent_index != -1)
				{
					current_node = closed[current_node.parent_index];
					path.unshift(current_node);
				}

				return path;
			}

			//Remove the current node from our open list
			open.splice(best_node, 1);

			//Push it onto the closed list
			closed.push(current_node);

			//Expand our current node (look in all 8 directions)
			for (var new_node_x = Math.max(0, current_node.x-1); new_node_x <= Math.min(columns-1, current_node.x+1); new_node_x++)
				for (var new_node_y = Math.max(0, current_node.y-1); new_node_y <= Math.min(rows-1, current_node.y+1); new_node_y++)
				{
					if (!allow_diagonals)
					{
						if (new_node_x != current_node.x && new_node_y != current_node.y)
							continue;
					}

					if (grid[new_node_y][new_node_x] == 0 //If the new node is open
						|| (player_position.x == new_node_x && player_position.y == new_node_y)) //or the new node is our player_position
					{
						//See if the node is already in our closed list. If so, skip it.
						var found_in_closed = false;
						for (var i in closed)
							if (closed[i].x == new_node_x && closed[i].y == new_node_y)
							{
								found_in_closed = true;
								break;
							}

						if (found_in_closed)
							continue;

						//See if the node is in our open list. If not, use it.
						var found_in_open = false;
						for (var i in open)
							if (open[i].x == new_node_x && open[i].y == new_node_y)
							{
								found_in_open = true;
								break;
							}

						if (!found_in_open)
						{
							var new_node = new node(new_node_x, new_node_y, closed.length-1, -1, -1, -1);

							new_node.g = current_node.g + Math.floor(Math.sqrt(Math.pow(new_node.x-current_node.x, 2)+Math.pow(new_node.y-current_node.y, 2)));
							new_node.h = heuristic(new_node, player_position);
							new_node.f = new_node.g+new_node.h;

							open.push(new_node);
						}
					}
				}
		}
		return [];
	}

	return [];
}

//An A* heurisitic must be admissible, meaning it must never overestimate the distance to the goal.
//In other words, it must either underestimate or return exactly the distance to the goal.
function heuristic(current_node, player_position)
{
	//Find the straight-line distance between the current node and the player_position. (Thanks to id for the improvement)
	//return Math.floor(Math.sqrt(Math.pow(current_node.x-player_position.x, 2)+Math.pow(current_node.y-player_position.y, 2)));
	var x = current_node.x-player_position.x;
	var y = current_node.y-player_position.y;
	return x*x+y*y;
}


/* Each node will have six values: 
 X position
 Y position
 Index of the node's parent in the closed array
 Cost from current_position to current node
 Heuristic cost from current node to player_position
 Cost from current_position to player_position going through the current node
*/	

function node(x, y, parent_index, g, h, f)
{
	this.x = x;
	this.y = y;
	this.parent_index = parent_index;
	this.g = g;
	this.h = h;
	this.f = f;
}